#include<iostream>
#include<vector>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#include<cmath>

using namespace std;
 
typedef map<string, double> MSD;

//表达式类
//主要目的处理浮点数
class Expression
{
public:
	virtual double Evaluate(){ return 0; }
};

//常数类
class Constant :public Expression
{
public:
	double value;

	//新建类
	Constant(double value)
	{
		this->value = value;
	}

	//返回类的值
	double Evaluate()
	{
		return value;
	}
};

//运算类
class Operation :public Expression
{
public:
	Expression *left;
	char op;
	Expression *right;
	
	//新建类
	Operation(Expression *left, char op, Expression *right)
	{
		this->left = left;
		this->op = op;
		this->right = right;
	}
	
	//计算值
	double Evaluate()
	{
		//递归计算
		double x = left->Evaluate();
		double y = right->Evaluate();
		double sum = 0;
		//运算
		switch (op){
		case '+' : sum = x + y;
			   break;
		case '-' : sum = x - y;
			   break;
		case '*' : sum = x * y;
			   break;
		case '/' : if(y != 0){
				  sum =  x / y;
			   }else{
				   cout << "错误:除数为零" << endl;
				   exit(0);
			   }
			   break;
		case '^' : sum = pow( x, y);
			   break;
		}
		return sum;
	}
};

//用递归算法将字符串转换为树
//s起始位置，t结束位置
Expression *strToTree(string str, int s, int t)
{
	//去除包含整个当前表达式的括号
	while (s <= t&&str[s] == '('&&str[t] == ')')s++, t--;
	if (s > t)
		return new Constant(0);
	//findLetter找到字母，用以判断是否为未知数
	//findChar找到字符，用以判断是否存在运算符
	bool findChar = false;
	//括号标记
	int brackets = 0;
	//lastPS最后的加减法
	//lastMD最后的乘除
	int lastPS = -1, lastMD = -1;
 
	for (int i = s; i <= t; i++)
	{
		//当前位置不是常数
		if (str[i] != '.' && (str[i]<'0' || str[i]>'9'))
		{
				//不是常数，就是运算符或是不合法输入
				findChar = true;
				switch (str[i])
				{
				case '(' : 
					brackets++; 
					break;
				case ')' :
					brackets--; 
					break;
				//更新最后加减法的位置
				case '+' :
				case '-' :
					if (!brackets){
						 lastPS = i; 
					}
					break;
				//更新最后乘除法的位置
				case '*' :
				case '/' :
				case '^' :
					if (!brackets){
						lastMD = i;
					}	
					break;
				default :
					cout << "错误: 非法运算符" << endl;
					return nullptr;
				}
		}
	}
	//括号不匹配
	if (brackets != 0){
		cout << "错误: 括号不匹配" << endl;
		exit(0);
	}
	//从s到t都是常数
	if (findChar == false){
		return new Constant(stod(str.substr(s, t - s + 1)));
	}
	//从s到t是个运算
	//没有加减就用乘除
	if (lastPS == -1){
		lastPS = lastMD;
	}
	
	//乘除法优先级更高因此优先在加减处分割,即最后算加减法
	//递归
	return new Operation(strToTree(str, s, lastPS - 1), str[lastPS], strToTree(str, lastPS + 1, t));
}
 
